package 搜索.BFS;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;
/*
    解题思路：
        这题要求最短路径。第一时间想到BFS。
        我们可以先举一个例子[0,1,1,0][0,0,0,1][0,1,0,0][1,1,0,0]
        剩下的要看图解在博客上有记录
 */
public class 二进制矩阵中的最短路径_1091 {

    public int shortestPathBinaryMatrix(int[][] grid) {
        int[][] direction = new int[][]{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};//分别代表八个方向，比如{1，0}就是右

        int x = grid.length;//横坐标
        int y = grid[0].length;//纵坐标

        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();

        queue.add(new Pair<>(0, 0));//在队列中放入 第一步：{0,0}
        int step = 0;//步数

        while (!queue.isEmpty()) {//当队列中有东西的话

            step++;

            int size = queue.size();
            while (size-- > 0) {


                Pair<Integer, Integer> poll = queue.poll();//返回队列的第一个元素，并且在队列中将其删除
                int key = poll.getKey();//key和val存放了我们遍历的那个值的下标
                int val = poll.getValue();

                if (grid[key][val] == 1) {//即遍历到的那个值为1.证明此路不通
                    continue;
                }
                if (key == x - 1 && val == y - 1) {//该下标等于目标元素了，也就是正方形的最右下角那个元素
                    return step;
                }

                grid[key][val] = 1;//如果它既不是1也不是目标元素，我们在遍历过它后就把它置为1，这样就不会二次访问到它了
                //注意 有些题目要求不能改动原数组，这就需要自己新建一个数组来存放是否访问过该元素。该题无此要求，我就直接置1

                for (int i = 0; i < 8; i++) {//遍历八个方向找寻新的符合条件的数字
                    int newkey = key + direction[i][0];
                    int newval = val + direction[i][1];
                    if (newkey >= x || newkey < 0 || newval >= y || newval < 0) {//查看新的下标是否越界
                        continue;
                    }
                    queue.add(new Pair<>(newkey, newval));//把新的满足条件的下标放入队列
                }


            }
        }
        return -1;
    }
}
